1821F - Timber - CodeForces Solution

#include <bits/stdc++.h>
 
using namespace std;

#define forn(i, n) for(int i = 0; i < int(n); i++) 

const int MOD = 998244353;

int add(int a, int b){
	a += b;
	if (a >= MOD)
		a -= MOD;
	if (a < 0)
		a += MOD;
	return a;
}

int mul(int a, int b){
	return a * 1ll * b % MOD;
}

int binpow(int a, int b){
	int res = 1;
	while (b){
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}

int main(){
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	
	vector<int> fact(2 * n + 1), rfact(2 * n + 1);
	fact[0] = 1;
	for (int i = 1; i <= 2 * n; ++i) fact[i] = mul(fact[i - 1], i);
	rfact[2 * n] = binpow(fact[2 * n], MOD - 2);
	for (int i = 2 * n - 1; i >= 0; --i) rfact[i] = mul(rfact[i + 1], i + 1);
	auto cnk = [&](int n, int k){
		if (k < 0 || n < 0 || k > n) return 0;
		return mul(fact[n], mul(rfact[k], rfact[n - k]));
	};
	auto snb = [&](int n, int k){
		return cnk(n + k, k);
	};
	
	int pw2 = 1;
	int ans = 0;
	for (int i = m; i >= 0; --i){
		int cur = 0;
		if (n - (m - i) * 1ll * (k + 1) - i * 1ll * (2 * k + 1) >= 0)
			cur = mul(snb(n - (m - i) * (k + 1) - i * (2 * k + 1), m), mul(pw2, cnk(m, i)));
		ans = add(ans, i & 1 ? -cur : cur);
		pw2 = mul(pw2, 2);
	}
	
	printf("%d\n", ans);
}